{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Average of Levels in Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: averageOfLevels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的层平均值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非空二叉树的根节点<meta charset=\"UTF-8\" />&nbsp;<code>root</code>&nbsp;, 以数组的形式返回每一层节点的平均值。与实际答案相差&nbsp;<code>10<sup>-5</sup></code> 以内的答案可以被接受。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/09/avg1-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>[3.00000,14.50000,11.00000]\n",
    "<strong>解释：</strong>第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。\n",
    "因此返回 [3, 14.5, 11] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/09/avg2-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,15,7]\n",
    "<strong>输出：</strong>[3.00000,14.50000,11.00000]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数量在&nbsp;<code>[1, 10<sup>4</sup>]</code> 范围内</li>\n",
    "\t<li><code>-2<sup>31</sup>&nbsp;&lt;= Node.val &lt;= 2<sup>31</sup>&nbsp;- 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [average-of-levels-in-binary-tree](https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [average-of-levels-in-binary-tree](https://leetcode.cn/problems/average-of-levels-in-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[3,9,20,15,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        queue = collections.deque([root])\n",
    "        averages = []\n",
    "\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            level_sum = 0\n",
    "\n",
    "\n",
    "            for i in range(size):\n",
    "\n",
    "                level_sum += queue[0].val\n",
    "\n",
    "                if queue[0].left:\n",
    "                    queue.append(queue[0].left)\n",
    "                    \n",
    "                if queue[0].right:\n",
    "                    queue.append(queue[0].right)\n",
    "\n",
    "                queue.popleft()\n",
    "            \n",
    "            averages.append(level_sum/size)\n",
    "        \n",
    "        return averages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return None\n",
    "        queue = [0, root]\n",
    "        result = []\n",
    "        level_node = []\n",
    "        while len(queue) != 0:\n",
    "            node = queue.pop()\n",
    "\n",
    "            if node != 0:\n",
    "                level_node.append(node.val)\n",
    "\n",
    "                if node.left:\n",
    "                    queue.insert(0, node.left)\n",
    "                if node.right:\n",
    "                    queue.insert(0, node.right)\n",
    "            else:\n",
    "                if len(queue) != 0:\n",
    "                    queue.insert(0,0)\n",
    "                result.append(sum(level_node) / len(level_node))\n",
    "                level_node = []\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        from queue import Queue\n",
    "        queue1 = Queue()\n",
    "        queue1.put(root)\n",
    "        res = []\n",
    "        while not queue1.empty():\n",
    "            size = queue1.qsize()\n",
    "            count = 0\n",
    "            for i in range(size):\n",
    "                top = queue1.get()\n",
    "                count += top.val\n",
    "                if (top.left):\n",
    "                    queue1.put(top.left)\n",
    "                if (top.right):\n",
    "                    queue1.put(top.right)\n",
    "            res.append(count / size)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import sys\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sumList = []\n",
    "        self.numList = []\n",
    "    \n",
    "    def searchTree(self, root, level):\n",
    "        if root:\n",
    "            if len(self.sumList) == level:\n",
    "                self.sumList.append(root.val)\n",
    "                self.numList.append(1)\n",
    "            else:\n",
    "                self.sumList[level] += root.val\n",
    "                self.numList[level] += 1\n",
    "\n",
    "            self.searchTree(root.left, level+1)\n",
    "            self.searchTree(root.right, level+1)\n",
    "    \n",
    "    def averageOfLevels(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        \n",
    "        self.searchTree(root, 0)\n",
    "        listLen = len(self.sumList)\n",
    "     \n",
    "        for i in range(listLen):\n",
    "            self.sumList[i] /= self.numList[i]\n",
    "            \n",
    "        return self.sumList\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        \n",
    "        avgs = []\n",
    "        \n",
    "        def traverse_levels(root_node, level):\n",
    "            if not root_node:\n",
    "                return\n",
    "            \n",
    "            if len(avgs) <= level:\n",
    "                avgs.append([root_node.val, 1])\n",
    "            else:\n",
    "                avgs[level] = [avgs[level][0] + root_node.val, avgs[level][1] + 1]\n",
    "                \n",
    "            traverse_levels(root_node.left, level + 1)\n",
    "            traverse_levels(root_node.right, level + 1)\n",
    "            \n",
    "        traverse_levels(root, 0)\n",
    "        \n",
    "        return [float(total / num) for total, num in avgs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        def lev(root,level):\n",
    "            if not root:\n",
    "                return\n",
    "            if len(sol)<level:\n",
    "                sol.append([])\n",
    "            sol[level-1].append(root.val)\n",
    "            lev(root.left,level+1)\n",
    "            lev(root.right,level+1)\n",
    "\n",
    "            \n",
    "        sol=[[]]\n",
    "        lev(root,1)\n",
    "        for i in range(len(sol)):\n",
    "            sol[i]= sum(sol[i])/len(sol[i])\n",
    "            \n",
    "        return sol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        def averageBST(node, level, count, sum_val):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            if level >= len(count):\n",
    "                count.append(1)\n",
    "                sum_val.append(node.val)\n",
    "            else:\n",
    "                count[level] = count[level] + 1\n",
    "                sum_val[level] = sum_val[level] + node.val\n",
    "                \n",
    "            averageBST(node.left, level+1, count, sum_val)\n",
    "            averageBST(node.right, level+1, count, sum_val)\n",
    "            \n",
    "        node_cnt = []\n",
    "        node_sum = []\n",
    "        averageBST(root, 0, node_cnt, node_sum)\n",
    "        \n",
    "        average = []\n",
    "        for cnt, sum_val in zip(node_cnt, node_sum):\n",
    "            average.append(sum_val / cnt)    \n",
    "            \n",
    "        return average"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        def average(root, level, sumoflevel):\n",
    "            if root != None:\n",
    "                if level > len(sumoflevel):\n",
    "                    sumoflevel.append([root.val, 1])\n",
    "                else:\n",
    "                    sumoflevel[level - 1][0] += root.val\n",
    "                    sumoflevel[level - 1][1] += 1\n",
    "                average(root.left, level + 1, sumoflevel)\n",
    "                average(root.right, level + 1, sumoflevel)\n",
    "        sumoflevel = []\n",
    "        average(root, 1, sumoflevel)\n",
    "        averagelevel = []\n",
    "        for i in range(len(sumoflevel)):\n",
    "            averagelevel.append(sumoflevel[i][0] / sumoflevel[i][1])\n",
    "        return averagelevel\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        \n",
    "        if root is None:\n",
    "            return root\n",
    "        queue = [root]\n",
    "        layers = list()\n",
    "        while queue:\n",
    "            layer = []\n",
    "            new_queue = list()\n",
    "            for node in queue:\n",
    "                layer.append(node.val)\n",
    "                if node.left:\n",
    "                    new_queue.append(node.left)\n",
    "                if node.right:\n",
    "                    new_queue.append(node.right)\n",
    "            if len(layer)>0:\n",
    "                layers.append(layer)\n",
    "            queue = new_queue\n",
    "        \n",
    "        result = [sum(nums)/len(nums) for nums in layers]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root,'*']\n",
    "        result = []\n",
    "        level = []\n",
    "        while len(queue):\n",
    "            node = queue.pop(0)\n",
    "            if node=='*':\n",
    "                result.append(sum(level)/len(level))\n",
    "                if len(queue)==0:\n",
    "                    return result\n",
    "                level = []\n",
    "                queue.append('*')\n",
    "            else:\n",
    "                level.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            size_all = size\n",
    "            ave = 0\n",
    "            while size:\n",
    "                node = queue.pop(0)\n",
    "                ave+=node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                size-=1\n",
    "            res.append(ave/size_all)\n",
    "        return res\n",
    "        # print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        ret = []\n",
    "        if not root:\n",
    "            return ret\n",
    "        level = []\n",
    "        level.append(root)\n",
    "        end = root\n",
    "\n",
    "        level_sum = 0\n",
    "        length = 0\n",
    "        while len(level) != 0:\n",
    "            tmp = level.pop(0)\n",
    "            level_sum += tmp.val\n",
    "            length += 1\n",
    "            if tmp.right:\n",
    "                level.append(tmp.right)\n",
    "            if tmp.left:\n",
    "                level.append(tmp.left)\n",
    "            if tmp == end:\n",
    "                ret.append(level_sum / length)\n",
    "                level_sum = 0\n",
    "                length = 0\n",
    "                if len(level) != 0:\n",
    "                    end = level[-1]\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = collections.deque()\n",
    "        ans.append(root)\n",
    "        res = []\n",
    "        while ans:\n",
    "            size = len(ans)\n",
    "            sm = 0\n",
    "            for i in range(size):\n",
    "                node = ans.popleft()\n",
    "                sm += node.val\n",
    "                if node.left:\n",
    "                    ans.append(node.left)\n",
    "                if node.right:\n",
    "                    ans.append(node.right)\n",
    "            res.append(sm / size)\n",
    "        return res\n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        stack1 = [root, ]\n",
    "        stack2 = []\n",
    "        ans = []\n",
    "        while stack1:\n",
    "            ans.append(sum(node.val for node in stack1)/len(stack1))\n",
    "            for s in stack1:\n",
    "                if s.left: stack2.append(s.left)\n",
    "                if s.right: stack2.append(s.right)\n",
    "            stack1 = stack2\n",
    "            stack2 = []\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        res = []        \n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            ans = []\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                ans.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)          \n",
    "            res.append(sum(ans)/len(ans))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        queue = collections.deque([root])\n",
    "        ans = []\n",
    "        while queue:\n",
    "            count = 0\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                n = queue.popleft()\n",
    "                count += n.val\n",
    "                left = n.left\n",
    "                right = n.right\n",
    "                if(left):\n",
    "                    queue.append(left)\n",
    "                if(right):\n",
    "                    queue.append(right)\n",
    "            ans.append(count/size)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        result = []\n",
    "        self.dfs(root,0,result)\n",
    "        return [sum(i)/len(i) for i in result]\n",
    "    \n",
    "    def dfs(self, root:TreeNode, level:int, result:List[float]):\n",
    "        if not root:return\n",
    "        if len(result) == level:\n",
    "            result.append([])\n",
    "        result[level].append(root.val)\n",
    "        self.dfs(root.left,level+1,result)\n",
    "        self.dfs(root.right,level+1,result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        def dfs(root, level):\n",
    "            if not root:\n",
    "                return\n",
    "            if level < len(totals):\n",
    "                totals[level] += root.val\n",
    "                counts[level] += 1\n",
    "            else:\n",
    "                totals.append(root.val)\n",
    "                counts.append(1)\n",
    "            dfs(root.left, level+1)\n",
    "            dfs(root.right, level+1)\n",
    "        counts = list()\n",
    "        totals = list()\n",
    "        dfs(root, 0)\n",
    "        return [total/count for total, count in zip(totals, counts)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        queue_list = []\n",
    "        avg_list = []\n",
    "        queue_list.append(root)\n",
    "        # avg_list.append(root.val)\n",
    "        while len(queue_list):\n",
    "            q_len = len(queue_list)\n",
    "            sum_res = 0\n",
    "            for i in range(q_len):\n",
    "                cur_node = queue_list.pop(0)\n",
    "                sum_res += cur_node.val\n",
    "                if cur_node.left is not None:\n",
    "                    queue_list.append(cur_node.left)\n",
    "                if cur_node.right is not None:\n",
    "                    queue_list.append(cur_node.right)\n",
    "            avg_list.append(sum_res/q_len)\n",
    "        return avg_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        res=[]\n",
    "        queue=collections.deque([root])\n",
    "        while queue:\n",
    "            total=0\n",
    "            size=len(queue)\n",
    "            for _ in range(size):\n",
    "                node=queue.popleft()\n",
    "                total+=node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(total/size)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        queue = deque()\n",
    "        result = []\n",
    "        if root!=None:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            lenth = len(queue)\n",
    "            tmp = 0\n",
    "            for i in range(lenth):\n",
    "                node = queue.popleft()\n",
    "                tmp += node.val\n",
    "                if i == lenth - 1:\n",
    "                    tmp = tmp / lenth\n",
    "                if node.left!=None:\n",
    "                    queue.append(node.left)\n",
    "                if node.right!=None:\n",
    "                    queue.append(node.right)\n",
    "            result.append(tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        queue = collections.deque([])\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            sum_=0\n",
    "            for i in range(n):\n",
    "                x = queue.popleft()\n",
    "                sum_ +=x.val\n",
    "                if x.left:\n",
    "                    queue.append(x.left)\n",
    "                if x.right:\n",
    "                    queue.append(x.right)\n",
    "            res.append(sum_/n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: TreeNode) -> List[float]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [(root, 0)]\n",
    "        level_sum = []\n",
    "        level_size = []\n",
    "        while queue:\n",
    "            node, level = queue.pop(0)\n",
    "            if level < len(level_sum):\n",
    "                level_sum[level] += node.val\n",
    "                level_size[level] += 1\n",
    "            else:\n",
    "                level_sum.append(node.val)\n",
    "                level_size.append(1)\n",
    "            if node.left: queue.append((node.left, level + 1))\n",
    "            if node.right: queue.append((node.right, level + 1))\n",
    "        return [level_sum[i] / level_size[i] for i in range(len(level_sum))]\n",
    "#637"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# 记录每层节点的值，使用mean()\n",
    "# class Solution:\n",
    "#     def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "#         res = []\n",
    "#         from collections import deque\n",
    "#         queue = deque([root])\n",
    "#         while queue:\n",
    "#             res_eachlevel = []\n",
    "#             for i in range(len(queue)):\n",
    "#                 cur = queue.popleft()\n",
    "#                 res_eachlevel.append(cur.val)\n",
    "#                 if cur.left:\n",
    "#                     queue.append(cur.left)\n",
    "#                 if cur.right:\n",
    "#                     queue.append(cur.right)\n",
    "#             res.append(mean(res_eachlevel))\n",
    "#         return res\n",
    "\n",
    "# 不记录每层节点的值，不使用mean()\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        res = []\n",
    "        from collections import deque\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            sum = 0\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                cur = queue.popleft()\n",
    "                sum += cur.val\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "            res.append(sum/size)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        # ans = []\n",
    "        # if not root:\n",
    "        #     return ans \n",
    "        # queue = [root]\n",
    "        # while queue:\n",
    "        #     total = 0\n",
    "        #     size = len(queue)\n",
    "        #     for _ in range(size):\n",
    "        #         node = queue.pop(0)\n",
    "        #         total += node.val\n",
    "        #         if node.left:\n",
    "        #             queue.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             queue.append(node.right)\n",
    "        #     ans.append(total / size)\n",
    "        # return ans\n",
    "\n",
    "        sums = []\n",
    "        cnts = []\n",
    "        def dfs(node, level):\n",
    "            if not node:\n",
    "                return\n",
    "            if level >= len(sums):\n",
    "                sums.append(node.val)\n",
    "                cnts.append(1)\n",
    "            else:\n",
    "                sums[level] += node.val\n",
    "                cnts[level] += 1\n",
    "            dfs(node.left, level + 1)\n",
    "            dfs(node.right, level + 1)\n",
    "        dfs(root, 0)\n",
    "        return [sum / cnt for sum, cnt in zip(sums, cnts)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            s = 0\n",
    "            for i in range(n):\n",
    "                node = queue.pop(0)\n",
    "                s += node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(s/n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            vals = []\n",
    "            for _ in range(len(queue)):\n",
    "                root = queue.pop(0)\n",
    "                vals.append(root.val)\n",
    "                if root.left:\n",
    "                    queue.append(root.left)\n",
    "                if root.right:\n",
    "                    queue.append(root.right)\n",
    "            res.append(sum(vals) / len(vals))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        if not root:\n",
    "            return[]\n",
    "        queue=collections.deque()\n",
    "        queue.append(root)\n",
    "        res=[]\n",
    "        while queue:\n",
    "            stage=[]#存储每一层的节点\n",
    "            for _ in range(len(queue)):\n",
    "                node=queue.popleft()\n",
    "                stage.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            if stage:\n",
    "                res.append(sum(stage)/len(stage))\n",
    "                #()//()是相除取整数\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        \n",
    "        dic = {}\n",
    "        \n",
    "        def dfs(root, level):\n",
    "            if not root:\n",
    "                return\n",
    "            else:\n",
    "                if level not in dic:\n",
    "                    dic[level] = [root.val]\n",
    "                else:\n",
    "                    dic[level] = dic[level] + [root.val]\n",
    "                dfs(root.left, level + 1)\n",
    "                dfs(root.right, level +1)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "\n",
    "        res = []\n",
    "        for i in dic.keys():\n",
    "            value = sum(dic[i])/len(dic[i])\n",
    "            res.append(value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        \n",
    "        def f(node: TreeNode, depth: int):\n",
    "            if not node: \n",
    "                return \n",
    "            if depth == len(sum):\n",
    "                sum.append(node.val)\n",
    "                num.append(1)\n",
    "            else:\n",
    "                sum[depth] += node.val\n",
    "                num[depth] += 1\n",
    "            f(node.right, depth + 1)\n",
    "            f(node.left, depth + 1)\n",
    "        sum = list()\n",
    "        num = list()\n",
    "        f(root, 0)\n",
    "        for i in range(len(num)):\n",
    "            num[i] = sum[i] / num[i]\n",
    "        return num"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
